package leetcode_2401_2500;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeeCode_2488_2_timeout {
    public static void main(String[] args) {
        System.out.println(countSubarrays(new int[]{3, 2, 1, 4, 5}, 4));
//        System.out.println(countSubarrays(new int[]{2,3,1}, 3));
//        System.out.println(countSubarrays(new int[]{5,19,11,15,13,16,4,6,2,7,10,8,18,20,1,3,17,9,12,14}, 6));
    }
    private static int countSubarrays(int[] nums, int k) {
        int len = nums.length;
        int start = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == k){
                nums[i] = 0;
                start = i;
                continue;
            }
            nums[i] = nums[i] < k ? -1 : 1;
        }
        int[] res = new int[1];
        Set<String> used = new HashSet<>();
        search(nums,0, start, start, res, used);
        return res[0];
    }
    private static void search(int[] table, int sum, int l, int r, int[] res, Set<String> used){
        if (used.contains(l + "-" + r))
            return;
        used.add(l + "-" + r);
        if (sum == 0 || sum == 1){
            //System.out.println(Arrays.toString(Arrays.copyOfRange(table, l, r + 1)) + " -> " +sum);
            res[0]++;
        }
        if (r + 1 < table.length){
            search(table, sum + table[r + 1], l, r + 1, res,used);
        }
        if (l - 1 >= 0){
            search(table, sum + table[l - 1], l - 1, r, res,used);
        }
    }
}
